package HanJiaHomeWork;

import LinkedList.ListNode;

import java.util.HashMap;

/**
 * 从链表中删去总和值为零的连续节点
 * 给你一个链表的头节点head，请你编写代码，反复删去链表中由 总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 *
 * 删除完毕后，请你返回最终结果链表的头节点。
 * 你可以返回任何满足题目要求的答案。
 * （注意，下面示例中的所有序列，都是对ListNode对象序列化的表示。）
 * 示例 1：
 * 输入：head = [1,2,-3,3,1]
 * 输出：[3,1]
 * 提示：答案 [1,2,1] 也是正确的。
 *
 * 示例 2：
 * 输入：head = [1,2,3,-3,4]
 * 输出：[1,2,4]
 */
public class day10_1 {
    public ListNode removeZeroSumSublists(ListNode head) {
        HashMap<Integer,ListNode> sumMap = new HashMap<>();
        ListNode dummy = new ListNode(0);
        int sum = 0;
        ListNode p = head;//当前节点
        sumMap.put(0,dummy);
        while(p != null){
            sum += p.val;
            if(sumMap.containsKey(sum)){
                ListNode node = sumMap.get(sum);
                ListNode del = node.next;
                node.next = p.next;

                int sum1 = sum;
                while(del != p){
                    sum1 += del.val;
                    sumMap.remove(sum1);
                    del = del.next;
                }
            }else{
                sumMap.put(sum,p);
            }
            p = p.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {

    }
}
